package java_thinking.unit_16.source;

import java.util.Arrays;

/**
 * @Desc:   双轴快排
 * https://blog.csdn.net/Holmofy/article/details/71168530
 * @author: cww
 * @DateTime: 2019/4/25 18:52
 */

public class DualPivotQuickSort {
    public static void main(String[] args) {
        int[] a4 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        dualPivotQuickSort(a4);
        System.out.println(Arrays.toString(a4));
    }

    public static void dualPivotQuickSort(int[] items) {
        dualPivotQuickSort(items, 0, items.length - 1);
    }

    public static void dualPivotQuickSort(int[] items, int start, int end) {
        if (start < end) {
            //序列第一个值如果大于序列最后一个值
            if (items[start] > items[end]) {
                swap(items, start, end);
            }
            int pivot1 = items[start];
            int pivot2 = items[end];
            int i = start , j = end, k = start + 1;
            OUT_LOOP : while (k <= j) {
                if (items[k] < pivot1) {
                    swap(items, ++i, k);
                } else if (pivot2 >= items[k]) {

                } else {
                    while (items[--j] > pivot2) {
                        if (k >= j) {
                            break OUT_LOOP;
                        }
                    }
                    if (items[j] < pivot1) {
                        swap(items, k, j);
                        swap(items, ++i, k);
                    } else {
                        swap(items, j, k);
                    }
                }
                k++;
            }
            swap(items, start,i);
            swap(items, end, j);
            dualPivotQuickSort(items, start,i-1);
            dualPivotQuickSort(items, i + 1, j - 1);
            dualPivotQuickSort(items, j + 1, end);
        }
    }

    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
